package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * 1026. 节点与其祖先之间的最大差值
 * @author feizns
 * @since 2020/3/17
 */
public class MaxAncestorDiff {

    public static void main(String[] args) {
        System.out.println(maxAncestorDiff(create()));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(0);
        ret.right = new TreeNode(1);
        return ret;
    }

    public static int maxAncestorDiff(TreeNode root) {
        return root != null ? maxAncestorDiff(root, root.val, root.val) : 0;
    }

    private static int maxAncestorDiff(TreeNode root, int max, int min) {
        if ( root != null ) {
            if ( root.val > max )
                max = root.val;
            else if ( root.val < min )
                min = root.val;
            int diff = max - min;
            int lef = maxAncestorDiff(root.left, max, min);
            int rig = maxAncestorDiff(root.right, max, min);
            return Math.max(Math.max(diff, lef), rig);
        }
        return 0;
    }

}
